git merge 的（伪）形式化定义

文件

每个文件是一个以行为单位的序列，例如下面的文件：

a
bc
d

就是序列 $(a,bc,d)$，我们认为序列是 base-1 的，即从 $1$ 开始编号

文件 $A$ 的规模 $|A|$ 是序列的大小，在这个例子中为 $3$

hunk

定义对文件的原子操作（hunk） 为三元组 $(i,\text{len},\text{rep})$，其中 $\text{rep}$ 是一个以行为单位的序列（所以，你乐意的话，当然也可以视为一个文件），$(i,\text{len},\text{rep})$ 表示从原文件的第 $i$ 行开始，删除 $\text{len}$ 行，然后插入 $\text{rep}$

$M=(i,\text{len},\text{rep})$ 的规模 $|M|$ 是 $\text{len}+|\text{rep}|$，领域 $F(M)$ 是区间 $[i,i+\text{len}]$

脚本

每个脚本是 $i$ 互不相同的 hunk 的集合

$\text{apply}(A,P)$ 表示将脚本 $P$ 中的 hunk 按 $i$ 降序（为了保证位置稳定）依次应用到 $A$ 产生的新文件，举个例子：

文件 $A$ 如下：

a
bc
d

脚本 $P$ 如下：

那么 $\text{apply}(A,P)$ 就得到如下文件：

e
a
f
gh
d

脚本 $P$ 的规模 $|P|$ 是其中所有 hunk 规模的总和，在这个例子中为 $1+2=3$

脚本 $P$ 的领域 $F(P)$ 是其中所有 $\text{hunk}$ 领域的并集

diff

对文件 $A$,$B$，定义 $\text{diff}(A,B)$ ，结果是一个脚本，满足

这不构成一个定义，只是一个约束条件，实际结果通过 Myers diff algorithm 计算得到

merge

对文件 $A$,$B$，定义 $\text{merge}(A,B)$ ，结果是一个文件

如果 $F(P)\cap F(Q)=\mathrm{\varnothing }$，那么没有合并冲突，可以按下式自动合并：

否则，需要先解决合并冲突，然后合并

注意，如果你在两个分支分别修改了一个文件的相邻两行，这会产生合并冲突！因为此时，如果把前一行的行号记作 $k$ ，那么 $P=\{(k,1,\text{xxx})\}$，$Q=\{(k+1,1,\text{yyy})\}$，$F(P)=[k,k+1]$，$F(Q)=[k+1,k+2]$，这可以看作是 git 的一个小特性